#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node{ll d;ll v;};
vector<node> q;
node a[81010],r[81010];
bool cmp(const node a,const node b){
	if(a.v!=b.v)return a.v<b.v;
	return a.d<b.d;
}
ll n,q1,x,v,g;
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	q.push_back((node){2,-199999999});
	scanf("%lld%lld",&n,&q1);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i].v);
		a[i].d=i;
		r[i]=(node){i,a[i].v};
		//q.push_back((node){i,x});
	}
	sort(r+1,r+n+1,cmp);
	for(int i=1;i<=n;i++)q.push_back((node){r[i].d,r[i].v});
	for(int i=1;i<=q1;i++){
		scanf("%lld%lld",&g,&x);
		if(g==1){
			scanf("%lld",&v);
			ll l=1,r1=n,ans;
			while(l<=r1){
				ll mid=(l+r1)>>1;
				if(q[mid].v==a[x].v&&q[mid].d==a[x].d){
					ans=mid;
					break;
				}
				else if(q[mid].v>a[x].v||(q[mid].v==a[x].v&&q[mid].d>a[x].d))r1=mid-1;
				else if(q[mid].v<a[x].v||(q[mid].v==a[x].v&&q[mid].d<a[x].d))l=mid+1;
			}
			//cout<<"8888    "<<endl;
			q.erase(q.begin()+ans,q.begin()+ans+1);
			a[x].v=v;
			q.push_back((node){10001,2000000001});
			l=0,r1=n-1;
			while(l<=r1){
				ll mid=(l+r1)>>1;
				if(((a[x].v>q[mid].v)||(a[x].v==q[mid].v&&a[x].d>q[mid].d))&&((a[x].v<q[mid+1].v)||(a[x].v==q[mid+1].v&&a[x].d<q[mid+1].d))){
					q.insert(q.begin()+mid+1,a[x]);
					break;
				}
				else if((a[x].v<q[mid].v)||(a[x].v==q[mid].v&&a[x].d<q[mid].d))r1=mid-1;
				else if((a[x].v>q[mid+1].v)||(a[x].v==q[mid+1].v&&a[x].d>q[mid+1].d))l=mid+1;
				//cout<<l<<' '<<r1<<endl;
			}
			q.pop_back();
		}
		else{
			ll l=1,r1=n,ans;
			while(l<=r1){
				ll mid=(l+r1)>>1;
				if(q[mid].v==a[x].v&&q[mid].d==a[x].d){
					printf("%lld\n",mid);
					break;
				}
				else if(q[mid].v>a[x].v||(q[mid].v==a[x].v&&q[mid].d>a[x].d))r1=mid-1;
				else if(q[mid].v<a[x].v||(q[mid].v==a[x].v&&q[mid].d<a[x].d))l=mid+1;
			}
		}
	}
	return 0;
}
